package offer;

/**
 * @Author Elephas
 * @Date 2022/2/1
 **/
@FunctionalInterface
public interface LongestNiceSubString {
    /**
     * A string s is nice if, for every letter of the alphabet that s contains,
     * it appears both in uppercase and lowercase.
     * For example, "abABB" is nice because 'A' and 'a' appear, and 'B' and 'b' appear.
     * However, "abA" is not because 'b' appears, but 'B' does not.
     *
     * Given a string s, return the longest substring of s that is nice.
     * If there are multiple, return the substring of the earliest occurrence.
     * If there are none, return an empty string.
     *
     * @param s
     * @return
     */
    String longestNiceSubstring(String s);
}
class LongestNiceSubStringImpl1 implements LongestNiceSubString{
    static final String TEST_01 = "YazaAay";
    public static void main(String[] args) {
        String temp = new LongestNiceSubStringImpl1().longestNiceSubstring(TEST_01);
        return;
    }
    /**
     * 暴力解
     * 共有 (n + 1) * n / 2 个字串，
     * 考虑维护一个hash表，和一个平衡因子，当hash表中出现只有一个字母的元素时，不平衡因子+1，第二次出现时-1，三次及以上不变
     * @param s
     * @return
     */
    @Override
    public String longestNiceSubstring(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        int[] lowerCase = new int[26];
        int[] upperCase = new int[26];
        int balanceFactor;
        int maxLen = 0;
        for (int i = 0; i < dp.length; i++) {
            balanceFactor = 0;
            init(lowerCase,upperCase);
            char currentChar = s.charAt(i);
            balanceFactor = processBalanceFactor(currentChar,lowerCase,upperCase,balanceFactor);
            for (int j = i + 1; j < dp.length; j++) {
                char innerChar = s.charAt(j);
                balanceFactor = processBalanceFactor(innerChar,lowerCase,upperCase,balanceFactor);
                if(balanceFactor == 0){
                    dp[i][j] = true;
                    if((j - i) > maxLen){
                        maxLen = j - i;
                    }
                }
            }

        }
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp.length; j++) {
                if(dp[i][j] && j - i == maxLen){
                    return s.substring(i,j+1);
                }
            }
        }
        return "";
    }
    private int processBalanceFactor(char currentChar, int[] lowerCase, int[] upperCase,int balanceFactor){
        if(currentChar - 'a' >= 0 && currentChar - 'a' <= 25){
            // 小写
            lowerCase[currentChar - 'a']++;
            boolean cond1 = lowerCase[currentChar - 'a'] == 1;
            if(cond1 && upperCase[currentChar - 32 - 'A'] >= 1){
                balanceFactor--;
            }
            if(cond1 && upperCase[currentChar - 32 - 'A'] == 0){
                balanceFactor++;
            }
        }else{
            upperCase[currentChar - 'A']++;
            boolean cond1 = upperCase[currentChar - 'A'] == 1;
            if(cond1 && lowerCase[currentChar + 32 - 'a'] == 0){
                balanceFactor++;
            }
            if(cond1 && lowerCase[currentChar + 32 - 'a'] >= 1){
                balanceFactor--;
            }
        }
        return balanceFactor;
    }
    private void init(int[] lowerCase,int[] upperCase){
        for (int i = 0; i < lowerCase.length; i++) {
            lowerCase[i] = 0;
        }
        for (int i = 0; i < upperCase.length; i++) {
            upperCase[i] = 0;
        }
    }
}

class LongestNiceSubStringImpl2 implements LongestNiceSubString{

    private int maxPos;
    private int maxLen;

    @Override
    public String longestNiceSubstring(String s) {
        this.maxPos = 0;
        this.maxLen = 0;
        int types = 0;
        for (int i = 0; i < s.length(); i++) {
            types |= 1 << (Character.toLowerCase(s.charAt(i)) - 'a');
        }
        types = Integer.bitCount(types);
        for (int i = 1; i < types; i++) {
            check(s,i);
        }
        return s.substring(maxPos,maxPos + maxLen);
    }
    private void check(String s,int typeNum){
        int[] lowerCnt = new int[26];
        int[] upperCnt = new int[26];
        int cnt = 0;
        for (int r = 0, l = 0, total = 0; r < s.length(); r++) {
            int idx = Character.toLowerCase(s.charAt(r)) - 'a';
            if(Character.isLowerCase(s.charAt(r))){
                ++lowerCnt[idx];
                if(lowerCnt[idx] == 1 && upperCnt[idx] > 0){
                    ++cnt;
                }
            }else{
                ++upperCnt[idx];
                if(upperCnt[idx] ==  1 && lowerCnt[idx] > 0){
                    ++cnt;
                }
            }
            total += (lowerCnt[idx] + upperCnt[idx]) == l ? l : 0;
            while(total > typeNum){
                idx = Character.toLowerCase(s.charAt(l)) - 'a';
                total -= (lowerCnt[idx] + upperCnt[idx]) == l ? l : 0;
                if(Character.isLowerCase(s.charAt(l))){
                    --lowerCnt[idx];
                    if(lowerCnt[idx] == 0 && upperCnt[idx] > 0){
                        --cnt;
                    }
                }else{
                    --upperCnt[idx];
                    if(upperCnt[idx] == 0 && lowerCnt[idx] > 0){
                        --cnt;
                    }
                }
                ++l;
            }
            if(cnt == typeNum && r - l + 1 > maxLen){
                maxPos = l;
                maxLen = r - l + 1;

            }
        }
    }
}